package algorithm_diagram;

import java.util.Arrays;

//动态规划，将大问题分解成离散子问题来解决
//当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用；每种动态规划解决方案都涉及网格；单元格中的值通常就是要优化的值
public class DynamicProgramming {

    public static void main(String[] args) {
        longestCommonSubsequence();
    }

    //最长公共子序列
    private static void longestCommonSubsequence(){
        String wordA="sish";
        String wordB="fosh";

        int[][] arr=new int[wordA.length()][wordB.length()];
        for(int i=0;i<wordA.length();i++){
            for(int j=0;j<wordB.length();j++){
                if(wordA.charAt(i) == wordB.charAt(j)){
                    if(i>0 && j>0){
                        arr[i][j]=arr[i-1][j-1]+1;
                    }else{
                        arr[i][j]=1;
                    }
                }else{
                    if (i==0 && j>0){
                        arr[i][j]=arr[i][j-1];
                    }else if(j==0 && i>0){
                        arr[i][j]=arr[i-1][j];
                    }else if(i>0 && j>0){
                        arr[i][j]=Math.max(arr[i-1][j],arr[i][j-1]);
                    }else{
                        arr[i][j]=0;
                    }
                }
            }
        }

        for(int[] row:arr){
            System.out.println(Arrays.toString(row));
        }
    }
}
